﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 求素数
{
    class PrimeNumber
    {

        /// <summary>
        ///  素数算法一
        ///  取条件数的开根号数,对其取模即可
        /// </summary>
        /// <param name="num">输入的条件数</param>
        /// <returns>条件数以内的素数个数</returns>
        static Int32 PrimeNumber1(Int32 num)
        {
            Int32 primeCount = 0;  //素数个数
            Int32 current = 2;
            #region MyRegion
            //while (current < num)
            //{
            //    bool flags = true;
            //    Int32 facter = 2;       //每次从2循环
            //    Int32 temp = (Int32)Math.Sqrt(current);//素数判断范围上限
            //    while (facter <= temp)
            //    {
            //        if (current % facter == 0)
            //        {
            //            flags = false;
            //            break;
            //        }
            //        facter++;
            //    }
            //    if (flags)
            //    {
            //        primeCount++;
            //        Console.Write(current.ToString() + "\t");
            //    }
            //    current++;
            //} 
            #endregion



            Enumerable.Range(current, num).ToList().ForEach(item =>
            {
                bool flags = true;
                Int32 facter = 2;       //每次从2循环
                Int32 temp = (Int32)Math.Sqrt(item);//素数判断范围上限

                while (facter <= temp)
                {
                    if (item % facter == 0)
                    {
                        flags = false;
                        break;
                    }
                    facter++;
                }
                if (flags)
                {
                    primeCount++;
                    Console.Write(item.ToString() + "\t");
                }
            });
            return primeCount;
        }

        /// <summary>
        ///  素数算法一
        ///   一个合数(非质数)都能分解为若干个比它小的质数的乘积,
        ///   把以前的质数保存起来，只需判断是否能被比它小的质数整除即可，
        ///   结合上面的分析只需判断能否被不大于sqrt(n)的质数整除即可
        /// </summary>
        /// <param name="num">输入的条件数</param>
        /// <returns>条件数以内的素数个数</returns>
        static Int32 PrimeNumber2(Int32 num)
        {
            int count = 0;                                  //标记素数个数
            Int32[] primeCount = new Int32[num];            //保存比条件数小的素数
            primeCount[0] = 2;
            Enumerable.Range(3, num).ToList().ForEach(item =>
                        {
                            bool flags = true;
                            Int32 index = 0;       //每次从2循环
                            Int32 temp = (Int32)Math.Sqrt(item);//素数判断范围上限

                            while (primeCount[index] <= temp)
                            {
                                if (item % primeCount[index] == 0)
                                {
                                    flags = false;
                                    break;
                                }
                                index++;
                            }
                            if (flags)
                            {
                                count += 1;
                                primeCount[count] = item;
                            }
                        });
            primeCount.Where(p => p != 0).ToList().ForEach(p =>
            {
                Console.Write(p.ToString() + "\t");
            });
            return primeCount.Where(p => p != 0).Count();
        }



        static void Main(string[] args)
        {
            //Int32 temp = 200;
            //Int32 count = PrimeNumber1(temp);
            //Console.WriteLine("\n\t{0}以内的素数有{1}个。。。", temp, count);


            Int32 temp = 200;
            Int32 count = PrimeNumber2(temp);
            Console.WriteLine("\n\t{0}以内的素数有{1}个。。。", temp, count);


            Console.ReadKey();


        }


    }
}
